{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Bauer-Fike Eigenvalue Sensitivity Bound"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import numpy.linalg as la"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "In the Bauer-Fike eigenvalue sensitivity bound, an important observation is that, given a diagonalized matrix\n",
        "$$X^{- 1} A  X = D$$\n",
        "that is perturbed by an additive perturbation $E$\n",
        "$$X^{- 1} (A + E) X = D + F,$$\n",
        "and if we suppose that $\\mu$ is an eigenvalue of $A+E$ (and $D+F$), we have\n",
        "$$\\|(\\mu I - D)^{- 1}\\|^{- 1} = | \\mu - \\lambda _k |,$$\n",
        "where $\\lambda_k$ is the eigenvalue of $A$ (diagonal entry of $D$) closest to $\\mu$.\n",
        "\n",
        "This notebook illustrates this latter fact. To that end, let the following be $D$:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[0, 0, 0, 0, 0, 0],\n",
              "       [0, 1, 0, 0, 0, 0],\n",
              "       [0, 0, 2, 0, 0, 0],\n",
              "       [0, 0, 0, 3, 0, 0],\n",
              "       [0, 0, 0, 0, 4, 0],\n",
              "       [0, 0, 0, 0, 0, 5]])"
            ]
          },
          "execution_count": 4,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "D = np.diag(np.arange(6))\n",
        "D"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": [
        "mu = 2.1"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[ 2.1,  0. ,  0. ,  0. ,  0. ,  0. ],\n",
              "       [ 0. ,  1.1,  0. ,  0. ,  0. ,  0. ],\n",
              "       [ 0. ,  0. ,  0.1,  0. ,  0. ,  0. ],\n",
              "       [ 0. ,  0. ,  0. , -0.9,  0. ,  0. ],\n",
              "       [ 0. ,  0. ,  0. ,  0. , -1.9,  0. ],\n",
              "       [ 0. ,  0. ,  0. ,  0. ,  0. , -2.9]])"
            ]
          },
          "execution_count": 6,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "mu * np.eye(6) - D"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([[ 0.476,  0.   ,  0.   ,  0.   ,  0.   ,  0.   ],\n",
              "       [ 0.   ,  0.909,  0.   ,  0.   ,  0.   ,  0.   ],\n",
              "       [ 0.   ,  0.   , 10.   ,  0.   ,  0.   ,  0.   ],\n",
              "       [-0.   , -0.   , -0.   , -1.111, -0.   , -0.   ],\n",
              "       [-0.   , -0.   , -0.   , -0.   , -0.526, -0.   ],\n",
              "       [-0.   , -0.   , -0.   , -0.   , -0.   , -0.345]])"
            ]
          },
          "execution_count": 9,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "la.inv(mu * np.eye(6) - D).round(3)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "9.999999999999991"
            ]
          },
          "execution_count": 10,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "la.norm(la.inv(mu * np.eye(6) - D), 2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The actual norm doesn't matter--the norm of a diagonal matrix has to be the biggest (abs. value) diagonal entry:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "9.999999999999991"
            ]
          },
          "execution_count": 11,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "la.norm(la.inv(mu * np.eye(6) - D), np.inf)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 12,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "0.10000000000000009"
            ]
          },
          "execution_count": 12,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "1/ la.norm(la.inv(mu * np.eye(6) - D), 2)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that this matches the distance between $\\mu$ and the closest entry of $D$."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.2+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}